//二叉搜索树中第 K 小的元素
//测试链接：https://leetcode.cn/problems/kth-smallest-element-in-a-bst/
public class KthSmallest {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) {
            this.val = val;
        }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    int res = 0, ans = 0;

    public int kthSmallest(TreeNode root, int k) {
        if(root == null || res == k) return 0;  //加上剪枝提示效率

        kthSmallest(root.left,k);

        if(res == k) return ans; //剪枝
        res++;
        if( res == k ) {
            ans =  root.val;
            return ans;  //剪枝
        }
        kthSmallest(root.right,k);

        return ans;
    }
}
